package baseclass.a_sort.baseSort;

import baseclass.a_sort.ArraysTool;

import java.util.Arrays;

/**
 * 冒泡，选择，插入
 *
 * @date 2020/2/26 19:19
 */
public class BaseSort {
    public static void main(String[] args) {
        int[] arr = {7, 0, 4, 0, 2, 4, 6, 5, -3, 5};
        int[] copy = Arrays.copyOf(arr, arr.length);
        bubble(arr);
        select(copy);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(copy));

    }



    //冒泡稳定排序
    public static void bubble(int[] arr) {
        if (!ArraysTool.check(arr)) return;

        for (int i = 0; i < arr.length; i++) {
            //做一个优化
            boolean sorted = true;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    ArraysTool.swap(arr, j, j + 1);
                    sorted = false;
                }
            }
            //如果原本就是有序的，优化到O(N)
            if (sorted) break;
        }
    }

    //选择不稳定排序, 如 2 2 0 ,第一个2和0要交换
    public static void select(int[] arr) {
        if (!ArraysTool.check(arr)) return;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    ArraysTool.swap(arr, i, j);
                }
            }
        }
    }

    //插排，打牌
    public static void insert(int[] arr) {
        if (!ArraysTool.check(arr)) return;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i -1 ; j >= 0; j--) {
                if (arr[j] > arr[j +1]) {
                    ArraysTool.swap(arr, j, j + 1);
                }else {
                    //arr[j] < arr[j + 1], j之前已经有序
                    break;
                }
            }
        }
    }
}
